{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coin LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToChange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #硬币"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>: n = 5\n",
    "<strong> 输出</strong>：2\n",
    "<strong> 解释</strong>: 有两种方式可以凑成总金额:\n",
    "5=5\n",
    "5=1+1+1+1+1\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>: n = 10\n",
    "<strong> 输出</strong>：4\n",
    "<strong> 解释</strong>: 有四种方式可以凑成总金额:\n",
    "10=10\n",
    "10=5+5\n",
    "10=5+1+1+1+1+1\n",
    "10=1+1+1+1+1+1+1+1+1+1\n",
    "</pre>\n",
    "\n",
    "<p> <strong>说明：</strong></p>\n",
    "\n",
    "<p>注意:</p>\n",
    "\n",
    "<p>你可以假设：</p>\n",
    "\n",
    "<ul>\n",
    "<li>0 &lt;= n (总金额) &lt;= 1000000</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coin-lcci](https://leetcode.cn/problems/coin-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coin-lcci](https://leetcode.cn/problems/coin-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n // 25 + 1):\n",
    "            rest = n - i * 25\n",
    "            a, b = rest // 10, rest % 10 // 5\n",
    "            ans += (a + 1) * (a + b + 1)\n",
    "        return ans % 1000000007\n",
    "\n",
    "\n",
    "\n",
    "        # mod = 10**9 + 7\n",
    "        # coins = [25, 10, 5, 1]\n",
    "\n",
    "        # f = [1] + [0] * n\n",
    "        # for coin in coins:\n",
    "        #     for i in range(coin, n + 1):\n",
    "        #         f[i] += f[i - coin]\n",
    "        # return f[n] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache_one_five_ten = {}\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        s = 0\n",
    "        while n >= 0:\n",
    "            s += self.wayToChangeOneFiveTen(n)\n",
    "            n -= 25\n",
    "        return s % 1000000007\n",
    "\n",
    "    def wayToChangeOneFiveTen(self, n: int) -> int:\n",
    "        n = n // 5 * 5\n",
    "        if n in self.cache_one_five_ten:\n",
    "            return self.cache_one_five_ten[n]\n",
    "\n",
    "        s = 0\n",
    "        x = n // 5\n",
    "\n",
    "        if x % 2 == 1:\n",
    "            s = (2 + (x + 1)) // 2 * ((x + 1 - 2) // 2 + 1)\n",
    "        else:\n",
    "            s = (1 + (x + 1)) // 2 * ((x + 1 - 1) // 2 + 1)\n",
    "\n",
    "        self.cache_one_five_ten[n] = s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        #动态规划呗\n",
    "        #dp[i][k] 只用0..k种硬币表示i分\n",
    "        candidates = [1,5,10,25]\n",
    "        n //= 5\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i] = i+1\n",
    "\n",
    "        for k in range(2,len(candidates)):\n",
    "            for i in range(1,n+1):\n",
    "                j = i-candidates[k]//5\n",
    "                if j>=0:\n",
    "                    dp[i] = (dp[i]+dp[j]) % (10**9+7)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        cs,n=[1,2,5],n//5\n",
    "        r=[1]*(n+1)\n",
    "        for c in cs:\n",
    "            for i in range(c,n+1):\n",
    "                r[i]+=r[i-c]\n",
    "        return r[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        cs,n=[1,2,5],n//5\n",
    "        r=[1]*(n+1)\n",
    "        for c in cs:\n",
    "            for i in range(c,n+1):\n",
    "                r[i]+=r[i-c]\n",
    "        return r[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coin = [5, 10, 25]\n",
    "        import array\n",
    "        ret = array.array('l', [1] * (n + 1))\n",
    "\n",
    "        for i in range(3):\n",
    "            for v in range(coin[i], n + 1):\n",
    "                ret[v] += ret[v - coin[i]]\n",
    "        return ret[n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "\n",
    "        d = [1] + [0] * n\n",
    "        costs = [25, 10, 5]\n",
    "\n",
    "        for cost in costs:\n",
    "            for i in range(cost, n + 1):\n",
    "                d[i] += d[i - cost]\n",
    "\n",
    "        return sum(d) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        import numpy as np\n",
    "        f = np.zeros(n + 26, dtype=np.int)\n",
    "        f[0] = 1\n",
    "        for j in [1, 5, 10, 25]:\n",
    "            for i in range(1, n + 1):\n",
    "                f[i] = (f[i] + f[i - j]) % 1000000007\n",
    "        return int(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        coins= [0, 1, 5, 10, 25]\n",
    "        res = np.ones(n+1)\n",
    "        for i in range(2, len(coins)):\n",
    "            coin = coins[i]\n",
    "            for j in range(coin, n+1):\n",
    "                res[j] = res[j] + res[j-coin]\n",
    "        return int(res[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        n=n//5\n",
    "        d=[1]\n",
    "        e=[1]\n",
    "        f=[1]\n",
    "        if n==0:\n",
    "            return 0\n",
    "        for i in range(1,n+1):\n",
    "            if i>=5:\n",
    "                d.append(d[i-5]+e[i-2]+f[i-1]+1)\n",
    "                e.append(e[i-2]+f[i-1]+1)\n",
    "                f.append(f[i-1]+1)\n",
    "            if 5>i>=2:\n",
    "                d.append(e[i-2]+f[i-1]+1)\n",
    "                e.append(e[i-2]+f[i-1]+1)\n",
    "                f.append(f[i-1]+1)\n",
    "            if 2>i:\n",
    "                d.append(f[i-1]+1)\n",
    "                e.append(f[i-1]+1)\n",
    "                f.append(f[i-1]+1)\n",
    "        return d[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp = {}\n",
    "        n = n//5\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        dp[2] = 4\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = i+1\n",
    "            if i>=2:\n",
    "                dp[i] += dp[i-2]%1000000007\n",
    "            if i>=5:\n",
    "                dp[i] += dp[i-5]%1000000007\n",
    "            if i>=7:\n",
    "                dp[i] -= dp[i-7]%1000000007\n",
    "            \n",
    "        return dp[n]%1000000007\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        '''\n",
    "        coins = [1,5,10,25]\n",
    "        coins_num = len(coins)\n",
    "        dp = np.array([[0]*(n+1) for _ in range(coins_num+1)])\n",
    "        dp[0,:] = 0\n",
    "        dp[:,0] = 1\n",
    "        for i in range(1,coins_num+1):\n",
    "            for j in range(1,n+1):\n",
    "                if j-coins[i-1] >= 0:\n",
    "                    dp[i,j] = (dp[i-1,j] + dp[i,j-coins[i-1]]) % 1000000007\n",
    "                else:\n",
    "                    dp[i,j] = (dp[i-1,j]) % 1000000007\n",
    "\n",
    "        return int(dp[coins_num,n])\n",
    "        '''\n",
    "        coins = [1,5,10,25]\n",
    "        coins_num = len(coins)\n",
    "        dp = np.array([0]*(n+1))\n",
    "        dp[0] = 1\n",
    "        for i in range(1,coins_num+1):\n",
    "            for j in range(1,n+1):\n",
    "                if j-coins[i-1] >= 0:\n",
    "                    dp[j] = (dp[j] + dp[j-coins[i-1]]) % 1000000007\n",
    "\n",
    "        return int(dp[n])\n",
    "\n",
    "\n",
    "        '''\n",
    "        #n = 5\n",
    "        choice = [1,5,10,25]\n",
    "        result = []\n",
    "        self.num_result = 0\n",
    "        def backtrace(T=[], S=0, choice=[]):\n",
    "            if sum(T) == n:\n",
    "                #result.append(T.copy())\n",
    "                self.num_result += 1\n",
    "                return\n",
    "            \n",
    "            #for c_ind in range(S, len(choice)):\n",
    "            for c_ind in range(0, len(choice)):\n",
    "                c = choice[c_ind]\n",
    "                if len(T) > 0 and c < T[-1]: continue\n",
    "                if sum(T) + c >n: continue\n",
    "                T.append(c)\n",
    "                backtrace(T, S+1, choice)\n",
    "                T.pop(-1)\n",
    "        backtrace([], 0, choice)\n",
    "        #print(result)\n",
    "        #return len(result)\n",
    "        return self.num_result\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        factor = n // 25\n",
    "        remainder = n % 25\n",
    "        cached_triple = {}\n",
    "        triple_sum = 0\n",
    "        for i in range(remainder % 10, n + 1, 10):\n",
    "            triple_sum += i // 5 + 1\n",
    "            cached_triple[i] = triple_sum\n",
    "        triple_sum = 0\n",
    "        for i in range((remainder + 5) % 10, n + 1, 10):\n",
    "            triple_sum += i // 5 + 1\n",
    "            cached_triple[i] = triple_sum\n",
    "        return sum(\n",
    "            cached_triple[n - twenty_five_count * 25]\n",
    "            for twenty_five_count in range(factor + 1)\n",
    "        ) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 788 ms ... 32 % ... 50.5 MB ... 79 %\n",
    "        #  time: O(n)\n",
    "        # space: O(n)\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        dp = [1] + [0] * n\n",
    "        for x in [1, 5, 10, 25]:\n",
    "            for i in range(1, n+1):\n",
    "                if i >= x:\n",
    "                    dp[i] = (dp[i] + dp[i-x]) % mod\n",
    "        return dp[-1]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = 1\n",
    "        for c in [1, 5, 10, 25]:\n",
    "            for i in range(1, n + 1):\n",
    "                if i - c >= 0:\n",
    "                    f[i] = (f[i] + f[i - c]) % 1000000007\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = int(1e9 + 7)\n",
    "N = int(1e6 + 1)\n",
    "d = [0] * N\n",
    "d[0] = 1\n",
    "for i in [1, 5, 10, 25]:\n",
    "    for j in range(N - i):\n",
    "        d[j + i] = (d[j + i] + d[j]) % mod\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        return d[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [1]+[0]*n\n",
    "        print(dp)\n",
    "        for j in [1, 5, 10, 25]:\n",
    "            for i in range(1, n+1):\n",
    "                if i>=j:\n",
    "                    dp[i] = (dp[i] + dp[i-j]) % mod\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [1] + [0] * n\n",
    "        coins = [1, 5, 10, 25]\n",
    "        print (dp)\n",
    "        for coin in coins:\n",
    "            for i in range(n):\n",
    "                if i + coin > n:\n",
    "                    break\n",
    "                dp[i + coin] = (dp[i + coin] + dp[i]) % mod\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        # 18:46~19:02 完全背包变种, dp滚动数组实现\n",
    "        M = int(1e9+7)\n",
    "        coins = [1, 5, 10, 25]\n",
    "        dp = [1] + [0 for _ in range(n)]\n",
    "        for c in coins:\n",
    "            for j in range(1, n+1):\n",
    "                if j >= c:\n",
    "                    dp[j] += dp[j-c]\n",
    "                    dp[j] %= M\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [1, 5, 10, 25]\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        for coin in coins:\n",
    "            for i in range(1, n+1):\n",
    "                if i >= coin:\n",
    "                    dp[i] += dp[i-coin]\n",
    "        return int(dp[-1] % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        my_list=[1]*(n+1)\n",
    "        my_list[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            my_list[i]=(i//25)+1\n",
    "        my_list2=[0]*(n+1)\n",
    "        for i in range(0,n+1,5):\n",
    "            temp1=int(i/5)\n",
    "            temp2=(temp1//2)+1\n",
    "            my_list2[i]=temp2\n",
    "        my_list2[0]=1\n",
    "        result=0\n",
    "        for i in range(0,n+1):\n",
    "            temp1=my_list[i]*my_list2[n-i]\n",
    "            result=result+temp1\n",
    "\n",
    "        return result%(10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        coins = [25, 10, 5, 1]\n",
    "\n",
    "        f = [1] + [0] * n\n",
    "        for coin in coins:\n",
    "            for i in range(coin, n + 1):\n",
    "                f[i] += f[i - coin]\n",
    "        return f[n] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        @lru_cache\n",
    "        def dfs(num,sums):\n",
    "            if sums==0:\n",
    "                return 1\n",
    "            res=0\n",
    "            for m in [25,10,5,1]:\n",
    "                if sums-m>=0 and m<=num:\n",
    "                    res+=dfs(m,sums-m)\n",
    "            return res\n",
    "        return dfs(25,n)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        s = set([1, 5, 10, 25])\n",
    "        for coin in s:\n",
    "            for i in range(1,n+1):\n",
    "                if i >= coin:\n",
    "                    dp[i] += dp[i-coin]\n",
    "                \n",
    "                    dp[i] %= 1000000007\n",
    "\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        f = [0] * (n + 1)\n",
    "        coins = [1, 5, 10, 25]\n",
    "        f[0] = 1\n",
    "        for i in range(4):\n",
    "            for j in range(coins[i], n + 1):\n",
    "                    f[j] += f[j - coins[i]]\n",
    "                    f[j] %= 1000000007\n",
    "        print(f)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        new_list = [1, 5, 10, 25]\n",
    "        dp = [[1] * (n + 1)] + [([1] + [0] * n) for _ in range(3)]\n",
    "\n",
    "        for i in range(1, 4):\n",
    "            for j in range( n + 1):\n",
    "                if j<new_list[i]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                    continue\n",
    "                if j%5==0:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i][j - new_list[i]]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "\n",
    "\n",
    "        return (dp[-1][-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "\n",
    "        coin = [25, 10, 5, 1]\n",
    "        dp = [[0] * (n+1) for _ in range(2)]\n",
    "        for i in range(len(coin) + 1):\n",
    "            dp[i % 2][0] = 1\n",
    "        \n",
    "        #dp[i][j] 表示使用i在前j个硬币的方法\n",
    "        for i in range(1, len(coin) + 1):\n",
    "            for j in range(n + 1):\n",
    "                dp[i % 2][j] = dp[(i - 1) % 2][j]\n",
    "                if j - coin[i-1] >= 0:\n",
    "                    dp[i % 2][j] += dp[i % 2][j - coin[i-1]]\n",
    "\n",
    "        return dp[len(coin) % 2][-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy \n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        res=[0]*(n+1)\n",
    "        coins=[25,10,5,1]\n",
    "        res[0]=1\n",
    "        for coin in coins:\n",
    "            for i in range(n+1):\n",
    "                if i-coin>=0:\n",
    "                    res[i]+=res[i-coin]\n",
    "        return res[-1]% 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp = [1]+[0]*n\n",
    "        mod = 10**9+7\n",
    "        coins = [1,5,10,25]\n",
    "        dp.append(1)\n",
    "        for coin in coins:\n",
    "            for i in range(coin,n+1):\n",
    "                dp[i] = dp[i] +dp[i-coin]\n",
    "        return dp[n]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp = [[0]*(n+1) for _ in range(4)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(4):\n",
    "            dp[i][0] = 1\n",
    "        coins = [25,10,5, 1]\n",
    "        for i in range(4):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if j - coins[i] >=0:\n",
    "                    dp[i][j] += dp[i][j-coins[i]]\n",
    "                dp[i][j] = dp[i][j] % 1000000007\n",
    "        return dp[3][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 10 10 5\n",
    "    # 10 5 5 5\n",
    "    # 5  5  5  5\n",
    "    # 5--->1  10----->2  25----> 3\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        # mod = 10**9 + 7\n",
    "        # coins = [25, 10, 5, 1]\n",
    "        # f = [1] + [0] * n\n",
    "        # for coin in coins:\n",
    "        #     for i in range(coin, n + 1):\n",
    "        #         f[i] += f[i - coin]\n",
    "        # return f[n] % mod\n",
    "        # F[i][j] 前i个硬币的，价值为j的方案数\n",
    "        coins = [25, 10, 5, 1]\n",
    "        f = [[0] * (n+1) for _ in range(len(coins))]\n",
    "        for i in range(len(f)):\n",
    "            for j in range(len(f[i])):\n",
    "                if j == 0:\n",
    "                    f[i][j] = 1\n",
    "        for i in range(0, len(coins)):\n",
    "            # print(f'coins:{coins[:i+1]}')\n",
    "            for j in range(1, n+1):\n",
    "                if j-coins[i] >= 0:\n",
    "                    f[i][j] = f[i-1][j] + f[i][j-coins[i]]\n",
    "                    # print(f'新增组合最后一个coin:{coins[i]} j:{j}')\n",
    "                else:\n",
    "                    f[i][j] = f[i - 1][j]\n",
    "                f[i][j] = f[i][j] % 1000000007\n",
    "        return f[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        dp=[1]+[0 for i in range(n)]\n",
    "        for j in [1,5,10,25]:\n",
    "            for i in range(1,n+1):\n",
    "                if i>=j:\n",
    "                    dp[i]=(dp[i]+dp[i-j])%1000000007\n",
    "        print(dp)\n",
    "        return dp[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = 1000000007\n",
    "        values = [1, 5, 10, 25]\n",
    "        dp = [i // 5 + 1 for i in range(n+1)]\n",
    "        for i in range(2, 4):\n",
    "            ndp = [0] * (n + 1)\n",
    "            for v in range(n+1):\n",
    "                if v - values[i] >= 0:\n",
    "                    ndp[v] = dp[v] + ndp[v-values[i]]\n",
    "                else:\n",
    "                    ndp[v] = dp[v]\n",
    "                ndp[v] = ndp[v] % mod\n",
    "            dp = ndp \n",
    "        return dp[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "\n",
    "        DP = [[0 for j in range(n+1)] for i in range(len(coins)+1)]\n",
    "        DP[0][0] = 1\n",
    "\n",
    "        for i in range(1, len(coins)+1):\n",
    "            for j in range(n+1):\n",
    "                # 不要\n",
    "                DP[i][j] = DP[i-1][j]  % 1000000007\n",
    "                # 要\n",
    "                if j-coins[i-1] >= 0:\n",
    "                    DP[i][j] = (DP[i][j] + DP[i][j-coins[i-1]]) % 1000000007\n",
    "\n",
    "        return DP[-1][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "        mod = 10**9 + 7\n",
    "        f = [[0] * (n + 1) for _ in range(5)]\n",
    "        f[0][0] = 1\n",
    "        for i, c in enumerate(coins, 1):\n",
    "            for j in range(n + 1):\n",
    "                f[i][j] = f[i - 1][j]\n",
    "                if j >= c:\n",
    "                    f[i][j] = (f[i][j] + f[i][j - c]) % mod\n",
    "        return f[-1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        list1 = [0 for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            list1[i] = 1\n",
    "        coins = [1,5,10,25]\n",
    "        for i in range(1,4):\n",
    "            list2 = [0 for _ in range(n+1)]\n",
    "            for j in range(n+1):\n",
    "                if j >= coins[i]:\n",
    "                    list2[j]=(list1[j]+list2[j-coins[i]])%1000000007\n",
    "                else:\n",
    "                    list2[j]=list1[j]\n",
    "            list1 = list2.copy()\n",
    "        return list2[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        s = [0] * (n+1)\n",
    "        s[0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            s[i] = (i) // 5 + 1\n",
    "        \n",
    "\n",
    "\n",
    "        s2 = [0] * (n+1)\n",
    "        s2[0] = 1\n",
    "        temp = [0] * 10\n",
    "        temp[0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            s2[i] = s[i] + temp[i%10]\n",
    "            temp[i%10] += s[i]\n",
    "\n",
    "        ans = s2[-1]\n",
    "        p = n - 25\n",
    "        while p >= 0:\n",
    "            ans += s2[p]\n",
    "            p -= 25\n",
    "        \n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, amount: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "        n = len(coins)\n",
    "\n",
    "        dp = [[0] * (amount+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(amount+1):\n",
    "                if j - coins[i] < 0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]]\n",
    "        return dp[-1][-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         self.result = 0\n",
    "#         record = {}\n",
    "#         def backtrack(n, sign1, sign2, sign3): # sign1: 1 ; sign2: 5; sign3:10\n",
    "#             if n == 0:\n",
    "#                 self.result += 1\n",
    "#                 self.result %= 1000000007\n",
    "#                 return \n",
    "#             if sign1 and sign2 and sign3 and n - 25 >= 0:\n",
    "#                 backtrack(n-25, 1, 1, 1)\n",
    "#             if sign1 and sign2 and n - 10 >= 0:\n",
    "#                 backtrack(n-10, 1, 1, 0)\n",
    "#             if sign1 and n - 5 >= 0:\n",
    "#                 backtrack(n-5, 1, 0, 1)\n",
    "#             if n - 1 >= 0:\n",
    "#                 backtrack(n-1, 0, 1, 1)\n",
    "#         backtrack(n, 1, 1, 1)\n",
    "#         return self.result\n",
    "\n",
    "## 完全背包--组合问题\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         record = {}\n",
    "#         def backtrack(n, sign):\n",
    "#             if n == 0:\n",
    "#                 return 1\n",
    "#             num = 0\n",
    "#             if n in record:\n",
    "#                 return record[n]\n",
    "#             for i in [25, 10, 5, 1]:\n",
    "#                 if i > sign:\n",
    "#                     continue\n",
    "#                 if n - i >= 0:\n",
    "#                     res = backtrack(n-i, i)\n",
    "#                     num += res\n",
    "#             record[n] = num\n",
    "#             return num\n",
    "#         backtrack(n, 25)\n",
    "#         return record[n]\n",
    "\n",
    "# 完全背包--组合问题\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        nums = [1, 5, 10, 25]\n",
    "        dp = []\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        res = list(dp)\n",
    "        for i in range(1, len(nums)+1):\n",
    "            for j in range(1, n+1):\n",
    "                if j - nums[i-1] >= 0:\n",
    "                    dp[j] = dp[j-nums[i-1]] +res[j]\n",
    "                    dp[j] %= 1000000007\n",
    "            res = list(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "# # 完全背包--组合问题\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         nums = [1, 5, 10, 25]\n",
    "#         dp = []\n",
    "#         # dp[i][j]代表的是使用i枚硬币达到金额j的组合数\n",
    "#         # 组合的规律是 dp[i][j] = dp[i][j-nums[j]] + dp[i-1][j]\n",
    "#         for i in range(len(nums)+1):\n",
    "#             dp.append([0]*(n+1))\n",
    "#         for i in range(len(nums)+1):\n",
    "#             dp[i][0] = 1\n",
    "#         for i in range(1, len(nums)+1):\n",
    "#             for j in range(1, n+1):\n",
    "#                 if j - nums[i-1] >= 0:\n",
    "#                     dp[i][j] = dp[i][j-nums[i-1]] + dp[i-1][j]\n",
    "#                     dp[i][j] %= 1000000007\n",
    "#                 else:\n",
    "#                     dp[i][j] = dp[i-1][j]\n",
    "#                     dp[i][j] %= 1000000007\n",
    "#         return dp[-1][-1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def waysToChange(self, amount: int) -> int:\n",
    "#         coins = [1, 5, 10, 25]\n",
    "#         if not amount:  ###注意，amount为0的情况下是1，全部选择数为0也是一个选择\n",
    "#             return 1\n",
    "#         if not coins:\n",
    "#             return 0\n",
    "#         dp = []\n",
    "#         for i in range(1+len(coins)):\n",
    "#             dp.append([0]*(amount+1)) # 只要满足了减到0，那么就是1了，在1的基础上，dp[1] = dp[0] \n",
    "#         for i in range(1+len(coins)):\n",
    "#             dp[i][0] = 1   \n",
    "#         for i in range(1, len(coins)+1):\n",
    "#             for j in range(1, amount+1): # 二维两者可以颠倒，但是一维不行！！\n",
    "#                 if j - coins[i-1] >= 0:\n",
    "#                     dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]\n",
    "#                     dp[i][j] %= 1000000007\n",
    "#                 else:\n",
    "#                     dp[i][j] = dp[i-1][j] % 1000000007\n",
    "        \n",
    "#         return dp[-1][-1] % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        row = [1] + [0] * (n)  # 总有一种方法拼出0元 那就是白给\n",
    "        dp = [ row.copy() for _ in range(len(coins) + 1)] # 这里多开了一行空间，防止i-1<0？\n",
    "\n",
    "        for i in range(1, len(coins) + 1): # i从1开始，为了确保i-1不会越界\n",
    "            # 有多少种硬币，就有多少种 转移方案\n",
    "\n",
    "            for j in range(1, n + 1):  #可以直接跳开0元的部分，毕竟都是1\n",
    "                dp[i][j] = dp[i - 1][j] # 毋庸置疑，一元的方案数可以直接转移，一定是等价的\n",
    "\n",
    "                if j >= coins[i - 1]:  # 当下标不越界时，符合状态转移条件 \n",
    "                    dp[i][j] += dp[i][j - coins[i - 1]]\n",
    "\n",
    "                dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[-1][-1] \n",
    "\n",
    "# class Solution:\n",
    "#     def change(self, amount: int, coins: List[int]) -> int:\n",
    "#         dp = [[0 for _ in range(len(coins) + 1)] for _ in range(amount + 1)]\n",
    "#         for j in range(len(coins) + 1):\n",
    "#             dp[0][j] = 1\n",
    "\n",
    "#         for i in range(amount + 1):\n",
    "#             for j in range(1, len(coins) + 1):\n",
    "#                 if i >= coins[j - 1]:\n",
    "#                     dp[i][j] = dp[i - coins[j - 1]][j] + dp[i][j - 1]\n",
    "#                 else:\n",
    "#                     dp[i][j] = dp[i][j - 1]\n",
    "#         return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "        dp = [[0] * (n+1) for _ in range(len(coins)+1)]\n",
    "        for row in range(len(dp)):\n",
    "            dp[row][0] = 1\n",
    "        for row in range(1, len(dp)):\n",
    "            for col in range(1, len(dp[0])):\n",
    "                if coins[row-1] > col:\n",
    "                    dp[row][col] = dp[row-1][col]\n",
    "                else:\n",
    "                    dp[row][col] = dp[row-1][col] + dp[row][col - coins[row-1]]\n",
    "        return dp[-1][-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp=[1]*(n+1)\n",
    "        for c in [5,10,25]:\n",
    "            if c>n:\n",
    "                break\n",
    "            cdp=[1]*(n+1)\n",
    "            \n",
    "            for i in range(1,n+1):\n",
    "                if i-c>=0:\n",
    "                    cdp[i]=cdp[i-c]+dp[i]\n",
    "                else:\n",
    "                    cdp[i]=dp[i]\n",
    "            dp=cdp\n",
    "\n",
    "\n",
    "        return dp[n]%(10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        c = [0, 25, 10, 5, 1]\n",
    "        dp = [[1] + [0] * n for _ in range(5)]\n",
    "        for i in range(1, 5):\n",
    "            for v in range(c[i], n+1):\n",
    "                dp[i][v] = dp[i-1][v] + dp[i][v - c[i]]\n",
    "        return dp[4][n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [25, 10, 5, 1]\n",
    "        dp = [[1]+[0]*(n) for _ in range(len(coins)+1)]\n",
    "        \n",
    "        for i in range(1,len(coins)+1):\n",
    "            for j in range(1,n+1):\n",
    "                if j-coins[i-1]>=0:\n",
    "                    dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        # print(dp)\n",
    "        return dp[-1][-1] % int(1e9+7)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def change(self, amount: int, coins: List[int]) -> int:\n",
    "#         dp = [[0 for _ in range(len(coins) + 1)] for _ in range(amount + 1)]\n",
    "#         for j in range(len(coins) + 1):\n",
    "#             dp[0][j] = 1\n",
    "\n",
    "#         for i in range(amount + 1):\n",
    "#             for j in range(1, len(coins) + 1):\n",
    "#                 if i >= coins[j - 1]:\n",
    "#                     dp[i][j] = dp[i - coins[j - 1]][j] + dp[i][j - 1]\n",
    "#                 else:\n",
    "#                     dp[i][j] = dp[i][j - 1]\n",
    "#         return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n):\n",
    "        if n == 0:\n",
    "            return n\n",
    "        c = [1, 5, 10, 25]\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(len(c)):\n",
    "            temp = [1] * (n + 1)\n",
    "            for v in range(1, n + 1):\n",
    "                if v >= c[i]:\n",
    "                    temp[v] = dp[v] + temp[v - c[i]]\n",
    "                else:\n",
    "                    temp[v] = dp[v]\n",
    "            dp = temp\n",
    "        return dp[n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        c_list =[1,5,10,25]\n",
    "        mod = 10**9 + 7\n",
    "        dp = [1] +[0]*n\n",
    "        new_dp = []\n",
    "        for i in range(4):\n",
    "            # print(dp,new_dp)\n",
    "            for j in range(len(dp)):\n",
    "                if j >= c_list[i]:\n",
    "                    new_dp.append(dp[j]+new_dp[-c_list[i]])\n",
    "                else:\n",
    "                    new_dp.append(dp[j])\n",
    "\n",
    "            dp = new_dp\n",
    "            new_dp = []\n",
    "        return dp[-1]%mod\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp1 = [1] * (n + 1)\n",
    "        dp2 = [1] * (n + 1)\n",
    "        coins = [5, 10, 25]\n",
    "        for coin in coins:\n",
    "            for i in range(coin, n + 1):\n",
    "                # freq = i // coin\n",
    "                # for f in range(freq + 1):\n",
    "                #     dp2[i] += dp1[i - f * coin]\n",
    "                dp2[i] = dp1[i] + dp2[i-coin]\n",
    "\n",
    "            dp1 = dp2.copy()\n",
    "        return dp1[n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        M = 1000000007\n",
    "        coins = [1, 5, 10, 25]\n",
    "        dp = [1] + [0] * n\n",
    "        for i in range(1, 5):\n",
    "            nxt = [1] + [0] * n\n",
    "            for j in range(1, n + 1):\n",
    "                nxt[j] = dp[j] + (nxt[j - coins[i - 1]] if j - coins[i - 1] >= 0 else 0)\n",
    "            dp = nxt\n",
    "        return dp[-1] % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        f5 = [0] * (n+1)\n",
    "        f10 = [0] * (n+1)\n",
    "        f25 = [0] * (n+1)\n",
    "        m = 1000000007\n",
    "        for i in range(5, n+1):\n",
    "            if i-5 >= 0:\n",
    "                f5[i] = 1\n",
    "                if i-5 > 0:\n",
    "                    f5[i] = (f5[i] + f5[i-5]) % m\n",
    "            if i-10 >= 0:\n",
    "                f10[i] = 1\n",
    "                if i-10 > 0:\n",
    "                    f10[i] = (f10[i] + f5[i-10] + f10[i-10]) % m\n",
    "            if i-25 >= 0:\n",
    "                f25[i] = 1\n",
    "                if i-25 > 0:\n",
    "                    f25[i] = (f25[i] + f5[i-25] + f10[i-25] + f25[i-25]) % m\n",
    "        return (f5[n]+f10[n]+f25[n]+1) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        dp = [[0 for i in range(n+1)] for j in range(4)]\n",
    "        def kind(m,n): # m 是最大面值，n是总分\n",
    "            if n<0:\n",
    "                return 0\n",
    "            if dp[m][n] == 0:\n",
    "                if n<0:\n",
    "                    return 0\n",
    "                elif n == 0:\n",
    "                    dp[m][n] = 1\n",
    "                    return 1\n",
    "                elif m == 0:\n",
    "                    dp[m][n] = 1\n",
    "                    return 1\n",
    "                else:\n",
    "                    if m == 1:\n",
    "                        dp[m][n] = kind(m, n-5) + kind(0, n)\n",
    "                        return dp[m][n]\n",
    "                    elif m == 2:\n",
    "                        dp[m][n] = kind(m, n-10) + kind(1, n)\n",
    "                        return dp[m][n]\n",
    "                    elif m == 3:\n",
    "                        dp[m][n] = kind(m, n-25) + kind(2, n)\n",
    "                        return dp[m][n]\n",
    "            else:\n",
    "                return dp[m][n]\n",
    "        a = kind(3,n)\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        c = [1, 5, 10, 25]\n",
    "        dp = [[0 for j in range(n+1)] for i in range(len(c))]\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(len(c)):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, len(c)):\n",
    "            for j in range(1, n+1):\n",
    "                if j - c[i] >= 0:\n",
    "                    dp[i][j] = (dp[i-1][j] + dp[i][j-c[i]])%1000000007\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]%1000000007\n",
    "        return dp[3][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "######################## 完全背包问题 + 背包问题方案数 ####################\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         nums = [1,5,10,25]\n",
    "#         m = len(nums)\n",
    "#         mod = 1000000007\n",
    "#         dp = [ [0]*(n+1) for i in range(m)]\n",
    "\n",
    "#         #dp[i][j]表示前i种硬币能构成价值j的总数\n",
    "#         for i in range(m):\n",
    "#             dp[i][0] = 1\n",
    "        \n",
    "#         for i in range(m):\n",
    "#             for j in range(1, n+1):\n",
    "#                 for k in range(0,i+1):\n",
    "#                     if j >= nums[k]:\n",
    "#                         dp[i][j] += (dp[k][j-nums[k]]) \n",
    "#                         dp[i][j] %= mod\n",
    "\n",
    "#         return dp[m-1][n]\n",
    "\n",
    "# # dp[i][j]等于，前i-1个元素组成j的组合数 + 前i-1个元素组成j-nums[i]的组合数 + 前i-1个元素组成j-2*nums[i]的组合数 ....\n",
    "# # 也就是包含0个nums[i]，1个nums[i]，2个nums[i]...的组合数\n",
    "# # 但是这种方法套了3层循环，很容易超时\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         nums = [1,5,10,25]\n",
    "#         m = len(nums)\n",
    "#         mod = 1000000007\n",
    "#         dp = [ [0]*(n+1) for i in range(m)]\n",
    "\n",
    "#         #dp[i][j]表示前i种硬币能构成价值j的组合总数\n",
    "#         for i in range(m):\n",
    "#             dp[i][0] = 1\n",
    "#         for i in range(0, n // nums[0]):\n",
    "#             dp[0][nums[0] * i] = 1\n",
    "\n",
    "#         for i in range(1, m):\n",
    "#             for j in range(1, n+1):\n",
    "#                 K = j // nums[i]\n",
    "#                 for k in range(0, K+1):\n",
    "#                     dp[i][j] += (dp[i-1][j-k*nums[i]])\n",
    "#                     dp[i][j] %= mod\n",
    "\n",
    "#         return dp[m-1][n]\n",
    "\n",
    "############################# 状态方程优化 ##################################\n",
    "# 令j=j-nums[i] 对状态转移方程进行优化，两式相减，得到dp[i][j] = dp[i][j-nums[i]] + dp[i-1][j]\n",
    "####### 一般这种转态方程中带求和运算的，都可以通过“两式相减”的方法进行优化 ########\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        nums = [1,5,10,25]\n",
    "        m = len(nums)\n",
    "        mod = 1000000007\n",
    "        dp = [ [0]*(n+1) for i in range(m)]\n",
    "\n",
    "        #dp[i][j]表示前i种硬币能构成价值j的组合总数\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] += dp[i][j-nums[i]]\n",
    "                    dp[i][j] %= mod\n",
    "\n",
    "        return dp[m-1][n]\n",
    "\n",
    "# ############################ 空间优化 ############################\n",
    "# # 因为dp[i][j] = dp[i][j-nums[i]] + dp[i-1][j]， dp[i][j]只与i的j-nums[i]列相关，所以内层循环要从小到大遍历\n",
    "# # dp[i][j]只与i-1的j-nums[i]列相关，内层循环就要从大到小遍历了，例如https://leetcode.cn/problems/partition-equal-subset-sum/\n",
    "# class Solution:\n",
    "#     def waysToChange(self, n: int) -> int:\n",
    "#         nums = [1,5,10,25]\n",
    "#         m = len(nums)\n",
    "#         mod = 1000000007\n",
    "#         dp = [0]*(n+1)\n",
    "\n",
    "#         dp[0] = 1\n",
    "\n",
    "#         #把上一行的数值初始化完毕\n",
    "#         for i in range(n//nums[0] +1):\n",
    "#             dp[i*nums[0]] = 1\n",
    "        \n",
    "#         for i in range(1,m):\n",
    "#             for j in range(1, n+1):\n",
    "#                 if j >= nums[i]:\n",
    "#                     dp[j] += dp[j-nums[i]]\n",
    "#                     dp[j] %= mod\n",
    "        \n",
    "#         return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        # coins = [25, 10, 5, 1]\n",
    "        coins = [25, 1, 10, 5]\n",
    "        dp = [[0] * (n + 1) for _ in range(4)]\n",
    "        for i in range(4):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for i in range(4):\n",
    "            for j in range(0, n + 1):\n",
    "                if j >= coins[i]:  # 如果容量够大\n",
    "                    dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i]]) % M\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        # print(\"\\n\".join([str(x) for x in dp]))\n",
    "        return dp[3][n]\n",
    "\n",
    "    def waysToChangeOptim(self, n: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        coins = [25, 10, 5, 1]\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for c in coins:\n",
    "            for i in range(c, n + 1):\n",
    "                dp[i] = (dp[i] + dp[i - c]) % M\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "    def waysToChangeStandard(self, n: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        coins = [25, 10, 5, 1]\n",
    "        # coins = [1, 5, 10, 25]\n",
    "        dp = [[0] * (n + 1) for _ in range(4)]\n",
    "        for i in range(4):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for i in range(4):\n",
    "            for j in range(coins[i], n + 1):\n",
    "                dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i]]) % M\n",
    "        print(\"\\n\".join([str(x) for x in dp]))\n",
    "        return dp[3][n]\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "class Solution {\n",
    "public:\n",
    "\n",
    "    //Speed Up\n",
    "    int waysToChange(int n){\n",
    "        int mo = 1000000007;\n",
    "        int coins[4] = {25, 10, 5, 1};\n",
    "        int dp[n + 1];\n",
    "        memset(dp, 0, sizeof(dp));\n",
    "\n",
    "        dp[0] = 1;\n",
    "        \n",
    "        for(int i = 0; i < 4; i++){\n",
    "\n",
    "            for(int j = coins[i]; j <= n; j++){\n",
    "                dp[j] = (dp[j] + dp[j - coins[i]]) % mo;\n",
    "            }\n",
    "        }\n",
    "        return dp[n];\n",
    "    }\n",
    "    int waysToChange2(int n) {\n",
    "        int coins[4] = {1, 5, 10, 25};\n",
    "        int dp[5][n + 1];\n",
    "        memset(dp, 0, sizeof(dp));\n",
    "        \n",
    "        for(int i = 0; i <= 4; i++){\n",
    "            dp[i][0] = 1;\n",
    "        }\n",
    "        \n",
    "\n",
    "        for(int i = 1; i <= 4; i++){\n",
    "            for(int j = 1; j <= n; j++){\n",
    "                for(int k = 0; k <= j / coins[i - 1]; k++){\n",
    "                    dp[i][j] += dp[i - 1][j - k * coins[i - 1]];\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "\n",
    "        return dp[4][n];\n",
    "\n",
    "        // bagpack full backpack\n",
    "        //\n",
    "        // f(i, j) = f(i - 1, v) + f(i - 1, v - Wi)\n",
    "        // number \n",
    "    }\n",
    "};\n",
    "\"\"\"       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [5, 25, 1, 10]\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, len(coins) + 1):\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1, n + 1):\n",
    "                if j >= coins[i - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        return dp[-1][-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        num = [0,1,5,10,25]\n",
    "        dp = [[0 for j in range(n+1)] for i in range(5)]\n",
    "        for j in range(n+1):\n",
    "            dp[1][j] = 1\n",
    "        for i in range(2, 5):\n",
    "            for j in range(n+1):\n",
    "                g = num[i]\n",
    "                j_tmp = j\n",
    "                if j >= g:\n",
    "                    dp[i][j] = (dp[i-1][j_tmp] + dp[i][j-g])%1000000007\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j_tmp]%1000000007\n",
    "        return dp[4][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        cost = [1,5,10,25]\n",
    "        dp = [[0] * (n + 1) for _ in range(len(cost) + 1)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "\n",
    "                if j - cost[i - 1] >= 0:\n",
    "                    dp[i][j] += dp[i][j - cost[i - 1]]\n",
    "                    dp[i][j] %= mod\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        # dp[i][j] 表示只通过前i种硬币, 币值为j的总表示方法\n",
    "        # 初始化为全0\n",
    "        dp = [[1 for j in range(n + 1)] for i in range(4)]\n",
    "        dp[0] = [1 for t in range(0, n+1)]\n",
    "        # 状态转移方程\n",
    "        #  不用第i种表示币值j的方案数  用第i种表示\n",
    "        # dp[i][j] = sum(dp[i-1][j - n*value[i]])\n",
    "        # dp[i][j+1] = sum(dp[i-1][j - n*value[i]]) = dp[i-1][j] + dp[i][j - value[i]]\n",
    "        values = [1, 5, 10, 25]\n",
    "        # 枚举i\n",
    "        for i in range(1, 4):\n",
    "            # 枚举j\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1, min(values[i], n+1)):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "            for j in range(values[i], n+1):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j - values[i]] \n",
    "                dp[i][j] %= 1000000007\n",
    "        return dp[3][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        # 动态规划\n",
    "        # dp[i][j]表示使用前i个硬币构成j的表示方法\n",
    "        # dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]\n",
    "        coins = [1,5,10,25]\n",
    "        dp = [[0 for i in range(0,n+1)] for j in range(0,len(coins)+1)]  # 初始化动态数组\n",
    "        dp[0] = [float('-inf')] * (n+1)  # 初始化使用0个硬币构成金额0,1,2,...,n的表示方法\n",
    "        for j in range(0,len(coins)+1):\n",
    "            dp[j][0] = 1  # 初始化使用j个硬币构成金额0的表示方法\n",
    "        \n",
    "        for i in range(1,len(coins)+1):\n",
    "            for j in range(1,n+1):\n",
    "                if j >= coins[i-1]:\n",
    "                    dp[i][j] = dp[i][j-coins[i-1]]%1000000007 + max(dp[i-1][j],0)%1000000007 # 使用前i个硬币构成金额j的表示方法\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],0)%1000000007\n",
    "        return dp[len(coins)][n]%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins = [1,5,10,25]\n",
    "        m = len(coins)\n",
    "        f = [[1]+[0 for _ in range(n)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(n+1):\n",
    "                f[i][j] = f[i-1][j]\n",
    "                if j >= coins[i-1]:\n",
    "                    f[i][j] = (f[i][j]+f[i][j-coins[i-1]])%1000000007\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        #分成至少用了1张最大面值的和一张都没用的，两种情况\n",
    "        c2 = []\n",
    "        for i in range(n + 1):\n",
    "            c2.append(i // 5 + 1)\n",
    "        c3 = c2[:10]\n",
    "        for i in range(10, n + 1):\n",
    "            c3.append(c2[i] + c3[i - 10])\n",
    "        c4 = c3[:25]\n",
    "        for i in range(25, n + 1):\n",
    "            c4.append(c3[i] + c4[i - 25])\n",
    "        return c4[-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        \n",
    "        dp = [[0 for _ in range(4)] for i in range(n + 1)]\n",
    "        dp[0] = [1,1,1,1]\n",
    "        for i in range(1, n + 1):\n",
    "            if i >= 25:\n",
    "                dp[i][0] = dp[i - 25][0] % MOD\n",
    "                dp[i][1] = (dp[i - 10][0] + dp[i - 10][1]) % MOD\n",
    "                dp[i][2] = (dp[i - 5][0] + dp[i - 5][1] + dp[i - 5][2]) % MOD\n",
    "                dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD\n",
    "            elif i >= 10:\n",
    "                dp[i][1] = dp[i - 10][1] % MOD\n",
    "                dp[i][2] = (dp[i - 5][1] + dp[i - 5][2]) % MOD\n",
    "                dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD\n",
    "            elif i >= 5:\n",
    "                dp[i][2] = dp[i - 5][2] % MOD\n",
    "                dp[i][3] = (dp[i - 1][2] + dp[i - 1][3]) % MOD\n",
    "            else:\n",
    "                dp[i][3] = dp[i - 1][3] % MOD\n",
    "        return sum(dp[n]) % MOD\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        big = int(1e9 + 7)\n",
    "        cand = [25, 10, 5, 1]\n",
    "        a = [[0] * len(cand) for _ in range(n + 1)]\n",
    "        for i in range(0, n + 1):\n",
    "            for j in range(len(cand)):\n",
    "                if i == 0:\n",
    "                    a[i][j] = 0\n",
    "                else:\n",
    "                    if i - cand[j] > 0:\n",
    "                        for k in range(j + 1):\n",
    "                            a[i][j] += a[i - cand[j]][k]\n",
    "                            a[i][j] %= big\n",
    "                    elif i - cand[j] == 0:\n",
    "                        a[i][j] += 1\n",
    "                    else:\n",
    "                        pass\n",
    "        return sum(a[-1])%big\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    x = Solution()\n",
    "    # for i in range(10):\n",
    "    #     print(i, x.waysToChange(i))\n",
    "    x.waysToChange(10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        # start 1159\n",
    "        # debug 1206 TLE 1212\n",
    "        # \n",
    "        cache = {}\n",
    "\n",
    "        # param num: number to count\n",
    "        # param coins: available coins to use in decending order\n",
    "        # return: number of combination\n",
    "        def dfs(num, coins):\n",
    "            if (num, tuple(coins)) in cache: return cache[(num, tuple(coins))]\n",
    "            if num == 0: return 1\n",
    "            if len(coins) == 1: return 1\n",
    "            coin = coins[0]\n",
    "            i, cnt = 0, 0\n",
    "            if num >= coin:\n",
    "                cnt += dfs(num - coin, coins)\n",
    "            cnt += dfs(num, coins[1:])\n",
    "            # while num >= i * coin:\n",
    "            #     cnt += dfs(num - i * coin, coins[1:])\n",
    "            #     i += 1\n",
    "            cache[(num, tuple(coins))] = cnt\n",
    "            return cnt % 1000000007\n",
    "\n",
    "        return dfs(n, [25,10,5,1])\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(idx, cur):\n",
    "            if cur < 0: return 0\n",
    "            if cur == 0: return 1\n",
    "            ret = 0\n",
    "            for i, c in enumerate(coins):\n",
    "                if i < idx:\n",
    "                    continue\n",
    "                ret += dfs(i, cur-c)\n",
    "            return ret% 1000000007\n",
    "\n",
    "        coins = [1, 5, 10, 25]\n",
    "        dp = [[0]*(n+1) for _ in range(4)]\n",
    "\n",
    "        for i in range(4):\n",
    "            for j in range(n+1):\n",
    "                if j == 0 or i == 0:\n",
    "                    dp[i][j] = 1\n",
    "                elif coins[i] <= j:\n",
    "                    dp[i][j] = dp[i][j-coins[i]]+dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        # for d in dp:\n",
    "        #     print(d)\n",
    "        return dp[-1][-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        coins=[1,5,10,25]\n",
    "        use=[i  for i in coins if i<=n]\n",
    "        dp=[[0 for i in range(n+1)] for j in range(len(use))]\n",
    "        for i in range(n+1):\n",
    "            dp[0][i]=1\n",
    "        for i in range(1,len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                if j>=coins[i]:\n",
    "                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return dp[-1][-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        ways_1 = [0]*1000001\n",
    "        ways_5 = [0]*1000001\n",
    "        ways_10 = [0]*1000001\n",
    "        ways_25 = [0]*1000001\n",
    "\n",
    "        ways_1[1] = 1\n",
    "        ways_5[5] = 1\n",
    "        ways_25[25] = 1\n",
    "        ways_10[10] = 1\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            ways_1[i] = ways_1[i-1]\n",
    "            if i > 10:\n",
    "                ways_10[i] = ways_10[i-10] + ways_5[i-10] + ways_1[i-10]\n",
    "            if i > 5:\n",
    "                ways_5[i] = ways_5[i-5] + ways_1[i-5]\n",
    "            if i > 25:\n",
    "                ways_25[i] = ways_25[i-25] + ways_10[i-25] + ways_5[i-25] + ways_1[i-25]\n",
    "\n",
    "        return (ways_1[n]+ways_5[n]+ways_10[n]+ways_25[n])%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return n\n",
    "        \n",
    "        coins = [1, 5, 10, 25]\n",
    "        m = len(coins)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = 1\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j >= coins[i - 1]:\n",
    "                    dp[i][j] += dp[i][j - coins[i - 1]]\n",
    "        \n",
    "        return dp[-1][-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToChange(self, n: int) -> int:\n",
    "        if n == 0: return 1\n",
    "        coins = [1, 5, 10, 25]\n",
    "        m = len(coins)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = 1\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            coin = coins[i-1]\n",
    "            for j in range(1, n+1):\n",
    "                k_max = j // coin\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if j >= coin:\n",
    "                    dp[i][j] += dp[i][j-coin]\n",
    "        \n",
    "        return dp[-1][-1] % 1000000007  \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
